Fast packet switching (known also as labelled packet switching or asynchronous time division switching) is a technique recently proposed for switching speech, data and video signals. According to this technique, information blocks, which are associated with a label characterizing the information and asynchronously arriving at the switching devices, are switched solely on the basis of the contents of such a label. Owing to protocol simplicity, this technique offers considerable performance improvements as to information processing rates and flexibility, as compared with conventional packet switching.
A switching exchange for a system employing such technique generally comprises an interconnection network composed of a plurality of identical elements combined into a certain number of successive stages, and a control structure. Depending on network size, user and/or system manager requirements, traffic characteristics, etc., different traffic distribution modalities as well as different embodiments of the interconnection network and the control structure are possible.
More particularly:
Traffic can be distributed at packet level (i.e. each packet follows its individual path independently of the other packets relevant to the same communication) or at virtual call level. In this case each virtual call is assigned a path through the network and hence all packets relevant to said call follow the same path.
The interconnection network can afford a single path or a plurality of alternative paths between an input and an output;
The control can be either a centralized control, in which a single unit controls all the node input/output lines and has at disposal all of the information necessary to forward the packets, or a distributed control. In the latter case a plurality of controllers are provided, each managing the traffic as to a certain group of input/output lines.
The present invention is applicable to distributed control networks, where a multiplicity of paths are available between an input and an output and traffic is distributed at the virtual call level. In a network of this kind, for each call to be switched the problem arises of choosing the best connection path between input and output, i.e. the path which optimizes certain predetermined parameters.
More particularly reference is often made to optimizing a "cost function" of the connection. The term "cost function" means a parameter related to bandwidth occupancy on the connection. Such parameter can be defined in various ways, depending on the characteristics of the switching elements forming the network.
A solution to this problem is described by M. De Pricker and M. De Somer in the paper entitled "Performance of a Service Independent Switching Network with Distributed Control", IEEE Journal on Selected Areas in Communication, Vol SAC-5, No. 8, October 1987. In this method, which can be applied to a network in which an output can be reached from an input via any central stage, a control packet is sent into the network to find a connection path between the desired input and output, which path is capable of guaranteeing an acceptable service quality. This path is looked for step-by-step, by using at each stage a local control function of the load of the stage output involved. More particularly, the load (as percentage of the occupied bandwidth as compared with the available bandwidth) due to the communications using at that instant that output is memorized in each switching element, and a check is made as to whether the additional load due to the new communication can be accepted, i.e. it does not lead to too high a queue overflow probability. If the control packet reaches the network output, the path thus found is then used for routing all packets of the same virtual communication.
This known method has the disadvantage that, due to the high number of alternative paths available between an input and an output, in order to find a routing path within a reasonable time without resorting to extremely complex evaluating algorithms, the path between adjacent stages is optimized but there is no global network vision, so that the path finally found is not necessarily the one which optimizes the global "cost function" of the new connection.